/**
 * 树结构转换工具函数
 */

/**
 * 数组转树结构
 * @param {Array} array - 数组数据
 * @param {Object} options - 配置选项
 * @returns {Array} 树结构数据
 */
export function arrayToTree(array, options = {}) {
  const {
    id = 'id',
    parentId = 'parentId',
    children = 'children',
    rootValue = null,
    strict = false,
  } = options;

  if (!Array.isArray(array)) {
    return [];
  }

  const result = [];
  const map = new Map();

  // 创建映射表
  array.forEach(item => {
    map.set(item[id], { ...item, [children]: [] });
  });

  // 构建树结构
  array.forEach(item => {
    const node = map.get(item[id]);
    const parent = item[parentId];

    if (parent === rootValue || parent === null || parent === undefined) {
      // 根节点
      result.push(node);
    } else {
      // 子节点
      const parentNode = map.get(parent);
      if (parentNode) {
        parentNode[children].push(node);
      } else if (strict) {
        throw new Error(`找不到父节点: ${parent}`);
      }
    }
  });

  return result;
}

/**
 * 树结构转数组
 * @param {Array} tree - 树结构数据
 * @param {Object} options - 配置选项
 * @returns {Array} 数组数据
 */
export function treeToArray(tree, options = {}) {
  const { children = 'children', includeChildren = false } = options;

  if (!Array.isArray(tree)) {
    return [];
  }

  const result = [];

  function traverse(nodes) {
    nodes.forEach(node => {
      const item = { ...node };

      if (includeChildren) {
        result.push(item);
      } else {
        const { [children]: _children, ...itemWithoutChildren } = item;
        result.push(itemWithoutChildren);
      }

      if (
        node[children] &&
        Array.isArray(node[children]) &&
        node[children].length > 0
      ) {
        traverse(node[children]);
      }
    });
  }

  traverse(tree);
  return result;
}

/**
 * 查找树节点
 * @param {Array} tree - 树结构数据
 * @param {Function|any} predicate - 查找条件
 * @param {Object} options - 配置选项
 * @returns {Object|null} 找到的节点
 */
export function findTreeNode(tree, predicate, options = {}) {
  const { children = 'children', findOne = true } = options;

  if (!Array.isArray(tree)) {
    return findOne ? null : [];
  }

  const result = findOne ? null : [];

  function traverse(nodes) {
    for (const node of nodes) {
      let match = false;

      if (typeof predicate === 'function') {
        match = predicate(node);
      } else {
        match = Object.keys(predicate).every(
          key => node[key] === predicate[key]
        );
      }

      if (match) {
        if (findOne) {
          return node;
        } else {
          result.push(node);
        }
      }

      if (
        node[children] &&
        Array.isArray(node[children]) &&
        node[children].length > 0
      ) {
        const childResult = traverse(node[children]);
        if (findOne && childResult) {
          return childResult;
        }
      }
    }
  }

  const found = traverse(tree);
  return findOne ? found : result;
}

/**
 * 查找树节点路径
 * @param {Array} tree - 树结构数据
 * @param {Function|any} predicate - 查找条件
 * @param {Object} options - 配置选项
 * @returns {Array} 节点路径
 */
export function findTreeNodePath(tree, predicate, options = {}) {
  const { children = 'children', pathKey = 'id' } = options;

  if (!Array.isArray(tree)) {
    return [];
  }

  function traverse(nodes, path = []) {
    for (const node of nodes) {
      const currentPath = [...path, node[pathKey]];

      let match = false;
      if (typeof predicate === 'function') {
        match = predicate(node);
      } else {
        match = Object.keys(predicate).every(
          key => node[key] === predicate[key]
        );
      }

      if (match) {
        return currentPath;
      }

      if (
        node[children] &&
        Array.isArray(node[children]) &&
        node[children].length > 0
      ) {
        const childPath = traverse(node[children], currentPath);
        if (childPath.length > 0) {
          return childPath;
        }
      }
    }
    return [];
  }

  return traverse(tree);
}

/**
 * 过滤树节点
 * @param {Array} tree - 树结构数据
 * @param {Function} predicate - 过滤条件
 * @param {Object} options - 配置选项
 * @returns {Array} 过滤后的树结构
 */
export function filterTree(tree, predicate, options = {}) {
  const { children = 'children', keepChildren = true } = options;

  if (!Array.isArray(tree)) {
    return [];
  }

  function filter(nodes) {
    return nodes.filter(node => {
      const matches = predicate(node);

      if (
        node[children] &&
        Array.isArray(node[children]) &&
        node[children].length > 0
      ) {
        const filteredChildren = filter(node[children]);

        if (keepChildren) {
          node[children] = filteredChildren;
        }

        return matches || (keepChildren && filteredChildren.length > 0);
      }

      return matches;
    });
  }

  return filter(tree);
}

/**
 * 映射树节点
 * @param {Array} tree - 树结构数据
 * @param {Function} mapper - 映射函数
 * @param {Object} options - 配置选项
 * @returns {Array} 映射后的树结构
 */
export function mapTree(tree, mapper, options = {}) {
  const { children = 'children' } = options;

  if (!Array.isArray(tree)) {
    return [];
  }

  function map(nodes) {
    return nodes.map(node => {
      const mappedNode = mapper(node);

      if (
        node[children] &&
        Array.isArray(node[children]) &&
        node[children].length > 0
      ) {
        mappedNode[children] = map(node[children]);
      }

      return mappedNode;
    });
  }

  return map(tree);
}

/**
 * 遍历树节点
 * @param {Array} tree - 树结构数据
 * @param {Function} callback - 遍历回调函数
 * @param {Object} options - 配置选项
 */
export function traverseTree(tree, callback, options = {}) {
  const {
    children = 'children',
    order = 'pre', // 'pre' | 'post'
  } = options;

  if (!Array.isArray(tree)) {
    return;
  }

  function traverse(nodes) {
    nodes.forEach(node => {
      if (order === 'pre') {
        callback(node);
      }

      if (
        node[children] &&
        Array.isArray(node[children]) &&
        node[children].length > 0
      ) {
        traverse(node[children]);
      }

      if (order === 'post') {
        callback(node);
      }
    });
  }

  traverse(tree);
}

/**
 * 计算树深度
 * @param {Array} tree - 树结构数据
 * @param {Object} options - 配置选项
 * @returns {number} 树深度
 */
export function getTreeDepth(tree, options = {}) {
  const { children = 'children' } = options;

  if (!Array.isArray(tree) || tree.length === 0) {
    return 0;
  }

  function getDepth(nodes, currentDepth = 0) {
    let maxDepth = currentDepth;

    nodes.forEach(node => {
      if (
        node[children] &&
        Array.isArray(node[children]) &&
        node[children].length > 0
      ) {
        const childDepth = getDepth(node[children], currentDepth + 1);
        maxDepth = Math.max(maxDepth, childDepth);
      }
    });

    return maxDepth;
  }

  return getDepth(tree);
}

/**
 * 获取树节点数量
 * @param {Array} tree - 树结构数据
 * @param {Object} options - 配置选项
 * @returns {number} 节点数量
 */
export function getTreeNodeCount(tree, options = {}) {
  const { children = 'children' } = options;

  if (!Array.isArray(tree)) {
    return 0;
  }

  let count = 0;

  function countNodes(nodes) {
    nodes.forEach(node => {
      count++;

      if (
        node[children] &&
        Array.isArray(node[children]) &&
        node[children].length > 0
      ) {
        countNodes(node[children]);
      }
    });
  }

  countNodes(tree);
  return count;
}

/**
 * 获取叶子节点
 * @param {Array} tree - 树结构数据
 * @param {Object} options - 配置选项
 * @returns {Array} 叶子节点数组
 */
export function getTreeLeaves(tree, options = {}) {
  const { children = 'children' } = options;

  if (!Array.isArray(tree)) {
    return [];
  }

  const leaves = [];

  function findLeaves(nodes) {
    nodes.forEach(node => {
      if (
        !node[children] ||
        !Array.isArray(node[children]) ||
        node[children].length === 0
      ) {
        leaves.push(node);
      } else {
        findLeaves(node[children]);
      }
    });
  }

  findLeaves(tree);
  return leaves;
}

/**
 * 获取节点层级
 * @param {Array} tree - 树结构数据
 * @param {Function|any} predicate - 查找条件
 * @param {Object} options - 配置选项
 * @returns {number} 节点层级（从0开始）
 */
export function getTreeNodeLevel(tree, predicate, options = {}) {
  const { children = 'children' } = options;

  if (!Array.isArray(tree)) {
    return -1;
  }

  function findLevel(nodes, level = 0) {
    for (const node of nodes) {
      let match = false;
      if (typeof predicate === 'function') {
        match = predicate(node);
      } else {
        match = Object.keys(predicate).every(
          key => node[key] === predicate[key]
        );
      }

      if (match) {
        return level;
      }

      if (
        node[children] &&
        Array.isArray(node[children]) &&
        node[children].length > 0
      ) {
        const childLevel = findLevel(node[children], level + 1);
        if (childLevel !== -1) {
          return childLevel;
        }
      }
    }
    return -1;
  }

  return findLevel(tree);
}

/**
 * 排序树节点
 * @param {Array} tree - 树结构数据
 * @param {Function|string} sortBy - 排序条件
 * @param {Object} options - 配置选项
 * @returns {Array} 排序后的树结构
 */
export function sortTree(tree, sortBy, options = {}) {
  const {
    children = 'children',
    order = 'asc', // 'asc' | 'desc'
  } = options;

  if (!Array.isArray(tree)) {
    return [];
  }

  function sort(nodes) {
    const sorted = [...nodes].sort((a, b) => {
      let aValue, bValue;

      if (typeof sortBy === 'function') {
        aValue = sortBy(a);
        bValue = sortBy(b);
      } else {
        aValue = a[sortBy];
        bValue = b[sortBy];
      }

      if (aValue < bValue) {
        return order === 'asc' ? -1 : 1;
      }
      if (aValue > bValue) {
        return order === 'asc' ? 1 : -1;
      }
      return 0;
    });

    return sorted.map(node => {
      if (
        node[children] &&
        Array.isArray(node[children]) &&
        node[children].length > 0
      ) {
        return {
          ...node,
          [children]: sort(node[children]),
        };
      }
      return node;
    });
  }

  return sort(tree);
}

/**
 * 扁平化树结构（保留层级信息）
 * @param {Array} tree - 树结构数据
 * @param {Object} options - 配置选项
 * @returns {Array} 扁平化数组
 */
export function flattenTree(tree, options = {}) {
  const {
    children = 'children',
    levelKey = 'level',
    pathKey = 'path',
  } = options;

  if (!Array.isArray(tree)) {
    return [];
  }

  const result = [];

  function flatten(nodes, level = 0, path = []) {
    nodes.forEach((node, index) => {
      const currentPath = [...path, index];
      const flattenedNode = {
        ...node,
        [levelKey]: level,
        [pathKey]: currentPath,
      };

      // 移除children属性
      delete flattenedNode[children];
      result.push(flattenedNode);

      if (
        node[children] &&
        Array.isArray(node[children]) &&
        node[children].length > 0
      ) {
        flatten(node[children], level + 1, currentPath);
      }
    });
  }

  flatten(tree);
  return result;
}

/**
 * 树结构验证
 * @param {Array} tree - 树结构数据
 * @param {Object} options - 配置选项
 * @returns {Object} 验证结果
 */
export function validateTree(tree, options = {}) {
  const { children = 'children', id = 'id', parentId = 'parentId' } = options;

  const result = {
    isValid: true,
    errors: [],
  };

  if (!Array.isArray(tree)) {
    result.isValid = false;
    result.errors.push('树结构必须是数组');
    return result;
  }

  const ids = new Set();
  const parentIds = new Set();

  function validate(nodes, level = 0) {
    nodes.forEach((node, index) => {
      // 检查必需字段
      if (!node[id]) {
        result.isValid = false;
        result.errors.push(`节点缺少id字段: 层级${level}, 索引${index}`);
      } else if (ids.has(node[id])) {
        result.isValid = false;
        result.errors.push(`重复的id: ${node[id]}`);
      } else {
        ids.add(node[id]);
      }

      if (node[parentId] !== undefined && node[parentId] !== null) {
        parentIds.add(node[parentId]);
      }

      // 检查children字段
      if (node[children] !== undefined) {
        if (!Array.isArray(node[children])) {
          result.isValid = false;
          result.errors.push(`节点${node[id]}的children字段必须是数组`);
        } else {
          validate(node[children], level + 1);
        }
      }
    });
  }

  validate(tree);

  // 检查父节点引用
  const orphanParentIds = [...parentIds].filter(parentId => !ids.has(parentId));
  if (orphanParentIds.length > 0) {
    result.isValid = false;
    result.errors.push(`存在孤立的父节点引用: ${orphanParentIds.join(', ')}`);
  }

  return result;
}
